package com.clstu.sort;

import java.util.Arrays;

/**
 * 研究快速排序(冒泡排序的升级版)
 */
public class QuickSort {
    public static void main(String[] args) {
        //测试一下
//        int[] arr = {2,7,3,4,2,2,2,2,5,6,7,1,8,2};
//        quickSort(arr,0,arr.length-1);
//        partition(arr,0,arr.length-1);
//        System.out.println("排序后:"+ Arrays.toString(arr));
        //测试速度(比较一下左神写的 和 尚硅谷的速度)
        int arrSize = 80000000;
        int[] arr = new int[arrSize];
        int[] arr1 = new int[arrSize];
        int[] arr2 = new int[arrSize];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=(int)(Math.random()*80000);
            arr1[i]=arr[i];
            arr2[i]=arr[i];
        }
        System.out.println("排序前arr是否有序:"+isSorted(arr)+" 排序前arr1是否有序:"+isSorted(arr1)+" 排序前arr2是否有序:"+isSorted(arr2));
        long start = System.currentTimeMillis();
        quickSort(arr1,0,arr1.length-1);
        long end = System.currentTimeMillis();
        System.out.println("快速排序(尚硅谷版)"+arr.length+"个数据耗时:"+(end-start)+"ms");//39ms,跟希尔排序一个量级,但是稍慢

        start = System.currentTimeMillis();
        quickSort2(arr2,0,arr2.length-1);
        end = System.currentTimeMillis();
        System.out.println("快速排序(左神版)"+arr.length+"个数据耗时:"+(end-start)+"ms");//15ms,优于尚硅谷版本,实测最快

        start = System.currentTimeMillis();
        quickSort2(arr2,0,arr2.length-1);
        end = System.currentTimeMillis();
        System.out.println("快速排序(左神版)(有序的)"+arr.length+"个数据耗时:"+(end-start)+"ms");//3ms(更快了,说明不会遇到最差情况)

        start = System.currentTimeMillis();
        quickSort3(arr,0,arr2.length-1);
        end = System.currentTimeMillis();
        System.out.println("快速排序(左神版3.0)"+arr.length+"个数据耗时:"+(end-start)+"ms");//25ms,优于尚硅谷版本,稍慢于上面版本
        System.out.println("排序后arr是否有序:"+isSorted(arr)+" 排序后arr1是否有序:"+isSorted(arr1)+" 排序后arr2是否有序:"+isSorted(arr2));
        //比较两个排序算法的排序结果是否一样
        System.out.println("排序后结果是否一样:"+same(arr1,arr2)+same(arr1,arr));
//        System.out.println("快速排序后(尚硅谷版):"+Arrays.toString(arr1));
//        System.out.println("快速排序后(左神版):"+Arrays.toString(arr2));

    }

    //编写方法实现快速排序(尚硅谷版,有点不理解,但是是对的)
    public static void quickSort(int[] arr,int left,int right){
        //思路:
        //快速排序过程:
        //1.找一个数,作为中间轴,先从最左边开始扫描中间轴左边的数,如果发现arr[l] >= pivot,扫描右边
        //                    从最右边开始扫描中间轴右边的数,如果arr[r] <= pivot,交换扫描停止后左右扫描到的数
                             //如果arr[r] == pivot 或者 arr[l] == pivot 会导致r和l同时都不动了,需要添加语句
        /*                     这两句话就是为了避免 l 和 r 同时不动出现死循环的局面的
                               if(arr[l]==pivot){
                                    r--;
                                }
                                if (arr[r]==pivot){
                                    l++;
                                }
         */
        //  直到两个扫描指针相等,break,此时中间轴左边的数都比中间轴小,中间轴右边的数都比中间轴大
        //2.左排序,递归左边
        //3.右排序,递归右边
        //如果可以直接退出
        int l = left;
        int r = right;
        int pivot = arr[(left+right)/2];//假设中间轴是中间的一个数
        int temp = 0;
        //扫描
        while (l<r){
            //扫描左边
            while (arr[l]<pivot){
                l++;
            }
            //扫描右边
            while (arr[r]>pivot){
                r--;
            }
            //如果扫描完
            if(l>=r){
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //下面两个if为了避免死循环的,如果arr[r] == pivot 或者 arr[l] == pivot 会导致r和l同时都不动了
            if(arr[l]==pivot){
                r--;
            }
            if (arr[r]==pivot){
                l++;
            }
        }
        if (r==l){
            r--;
            l++;
        }
        //左排序
        if(r>left) {//这个判断时为了避免出现只有一个数也排一次序,同时还能避免r<0(left)的情况(这样会产生数组越界异常!!!)
            quickSort(arr, left, r);
        }
        //右排序
        if(l<right) {//同上
            quickSort(arr, l, right);
        }
    }

    //编写方法实现partition,(左神版本快排)
    // 即将数组中规定一个中间轴pivot,小于pivot的放左边,等于pivot的放中间,大于pivot的放右边,返回两个边界
    public static int[] partition(int[] arr,int left,int right){
        //首先定义l,是小于pivot的边界,l左边的数一定都小于pivot
        //   定义r,是大于pivot的边界,l右边的数一定都大于pivot
        //过程:定义变量i,
        //    从左到右扫描整个数组,如果发现 < pivot,和小于区域的后一个数做交换,交换后i++,l++(小于区域扩充一个
        //                      如果发现> pivot,和大于区域的前一个数做交换,交换后i原地不动,r--(大于区域扩充一个
        //                             = pivot,就直接i++扫描下一个,
        // 到最后两个区域撞上的时候(i==r)就代表扫描完了,三个区域就一定划分好了
        int pivot = arr[(right+left)/2];
        int l = left-1;//小于边界,因为开始没有小于的数,为left-1
        int r = right+1;//大于的边界,因为开始没有大于的数,为left-1
        int i=left;//扫描指针
        int temp = 0;
        while (i!=r){
            //< pivot,和小于区域的后一个数做交换,交换后i++,l++(小于区域扩充一个
            if(arr[i]<pivot){
                temp = arr[i];
                arr[i] = arr[l+1];
                arr[l+1] = temp;
                l++;
                i++;
            }else if(arr[i]>pivot){
                //> pivot,和大于区域的前一个数做交换,交换后i原地不动,r--(大于区域扩充一个
                temp = arr[i];
                arr[i] = arr[r-1];
                arr[r-1] = temp;
                r--;
            }else {
                // = pivot,就直接i++扫描下一个,
                i++;
            }
        }
        return new int[]{l, r};
    }

    //编写方法实现快速排序(左神版,理解ok),实测最快!!!(经过实验证明,pivot选择中间的数确实更快)
    public static void quickSort2(int[] arr,int left,int right){
        //如果不用排序
        if(left>=right){
            return;
        }
        //假设中间轴pivot是中间的数,(不让两边的数做中间轴的原因是可以很容易的举出最差的例子,比如原本就有序反而排序更慢)
        //第一步,将小于大于等于pivot的数分别放在左边中间右边
        int pivot = arr[(left+right)/2];
        int l = left-1;
        int r = right+1;
        int i = left;
        int temp = 0;
        while (i<r){//区域撞上的时候就退出
            if (arr[i]<pivot){
                temp = arr[i];
                arr[i]=arr[l+1];
                arr[l+1]=temp;
                l++;
                i++;
            }else if(arr[i]>pivot){
                temp = arr[i];
                arr[i] = arr[r-1];
                arr[r-1]=temp;
                r--;
            }else {
                i++;
            }
        }
        //while结束后区域已经分好
        //左排序
        quickSort2(arr,left,l);
        //右排序
        quickSort2(arr,r,right);
    }

    //快排3.0,左神版,把所有情况都一视同仁,就不会右最坏情况了,不是最快,但是最稳定,仍快于尚硅谷版本
    public static void quickSort3(int[] arr,int left,int right){
        //如果不用排序
        if(left>=right){
            return;
        }
        //假设中间轴pivot是这个范围之间的等概率随机数
        //第一步,将小于大于等于pivot的数分别放在左边中间右边
        int pivot = arr[left+(int)(Math.random()*(right-left+1))];
        int l = left-1;
        int r = right+1;
        int i = left;
        int temp = 0;
        while (i<r){//区域撞上的时候就退出
            if (arr[i]<pivot){
                temp = arr[i];
                arr[i]=arr[l+1];
                arr[l+1]=temp;
                l++;
                i++;
            }else if(arr[i]>pivot){
                temp = arr[i];
                arr[i] = arr[r-1];
                arr[r-1]=temp;
                r--;
            }else {
                i++;
            }
        }
        //左排序
        quickSort3(arr,left,l);
        //右排序
        quickSort3(arr,r,right);
    }

    //编写方法判断两个数组的内容是否一样
    public static boolean same(int[] arr1,int[] arr2){
        for (int i = 0; i < arr1.length&&i<arr2.length; i++) {
            if(arr1[i]!=arr2[i]){
                return false;
            }
        }
        return true;
    }

    //编写方法判断数组是否已经有序
    public static boolean isSorted(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]>arr[i+1]) return false;
        }
        return true;
    }
}
